/*
 * @auther  yaoleilei<windowhero@sina.com>
 * @date    Fri Sep 22 20:45:49 CST 2017
 */
#ifndef __URLMATCH_H__
#define __URLMATCH_H__
#define _GNU_SOURCE
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <pthread.h>
#include <time.h>
#include "list.h"

#if 1
#define URLMATCH_LOG(fmt, ...)     printf("line %u: "fmt, __LINE__, ##__VA_ARGS__)
#define URLMATCH_ERR(fmt, ...)     printf("line %u: "fmt, __LINE__, ##__VA_ARGS__)
#else
#define URLMATCH_LOG(...)
#define URLMATCH_ERR(fmt, ...)     printf("line %u: "fmt, __LINE__, ##__VA_ARGS__)
#endif

#define URLMATCH_DEFAULT_CHAR_LIST "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.%~!@#$&*()=:/,;?+'-_`|[]{}\\"
#define URLMATCH_DEFAULT_CHAR_LIST_LEN (sizeof(URLMATCH_DEFAULT_CHAR_LIST) - 1)

#define URLMATCH_FULL_CHAR_LIST \
    "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f" \
    "\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f" \
    "\x20\x21\x22\x23\x24\x25\x26\x27\x28\x29\x2a\x2b\x2c\x2d\x2e\x2f" \
    "\x30\x31\x32\x33\x34\x35\x36\x37\x38\x39\x3a\x3b\x3c\x3d\x3e\x3f" \
    "\x40\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4a\x4b\x4c\x4d\x4e\x4f" \
    "\x50\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5a\x5b\x5c\x5d\x5e\x5f" \
    "\x60\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6a\x6b\x6c\x6d\x6e\x6f" \
    "\x70\x71\x72\x73\x74\x75\x76\x77\x78\x79\x7a\x7b\x7c\x7d\x7e\x7f" \
    "\x80\x81\x82\x83\x84\x85\x86\x87\x88\x89\x8a\x8b\x8c\x8d\x8e\x8f" \
    "\x90\x91\x92\x93\x94\x95\x96\x97\x98\x99\x9a\x9b\x9c\x9d\x9e\x9f" \
    "\xa0\xa1\xa2\xa3\xa4\xa5\xa6\xa7\xa8\xa9\xaa\xab\xac\xad\xae\xaf" \
    "\xb0\xb1\xb2\xb3\xb4\xb5\xb6\xb7\xb8\xb9\xba\xbb\xbc\xbd\xbe\xbf" \
    "\xc0\xc1\xc2\xc3\xc4\xc5\xc6\xc7\xc8\xc9\xca\xcb\xcc\xcd\xce\xcf" \
    "\xd0\xd1\xd2\xd3\xd4\xd5\xd6\xd7\xd8\xd9\xda\xdb\xdc\xdd\xde\xdf" \
    "\xe0\xe1\xe2\xe3\xe4\xe5\xe6\xe7\xe8\xe9\xea\xeb\xec\xed\xee\xef" \
    "\xf0\xf1\xf2\xf3\xf4\xf5\xf6\xf7\xf8\xf9\xfa\xfb\xfc\xfd\xfe\xff"
#define URLMATCH_FULL_CHAR_LIST_LEN 256

typedef struct urlmatch_pattern {
    struct urlmatch_pattern *next;
    void                    *userdata;
} urlmatch_pattern_t;

typedef struct urlmatch_state{
    struct list_head node;
    struct urlmatch_state   **next2;
    urlmatch_pattern_t      *urlmatch_pattern;
} urlmatch_state_t;

typedef void (*URLMATCH_USERFREE)(void *);

struct urlmatch {
    uint8_t *char_list;
    int     char_list_len;
    uint8_t X[256];
    unsigned state_count;
    unsigned item_count;
    uint64_t state_mem;
    uint64_t stat_array_mem;
    uint64_t stat_array_count;
    unsigned pattern_count;
    uint64_t pattern_mem;
    struct list_head state_list;
    urlmatch_state_t        root_state;
    URLMATCH_USERFREE       urlmatch_userfree;
};

static inline urlmatch_pattern_t *urlmatch_find_long_host(struct urlmatch *m, const char *host, int host_len)
{
    urlmatch_state_t *urlmatch_state = &m->root_state;
    urlmatch_pattern_t *urlmatch_pattern;
    urlmatch_pattern_t *urlmatch_pattern_last = NULL;
    int i;
    //printf("test host %.*s len %d\n", host_len, host, host_len);
    for (i = host_len-1; i >= 0; i--){
        //printf("test %c\n", host[i]);
        unsigned char next_state_pos = m->X[(unsigned char)host[i]];
        if (urlmatch_state->next2 == NULL) break;
        urlmatch_state = urlmatch_state->next2[next_state_pos]; if (urlmatch_state == NULL) break;
        for(urlmatch_pattern = urlmatch_state->urlmatch_pattern; urlmatch_pattern; urlmatch_pattern = urlmatch_pattern->next) {
            urlmatch_pattern_last = urlmatch_pattern;
        }
    }
    return urlmatch_pattern_last;
}

static inline urlmatch_pattern_t *urlmatch_find(struct urlmatch *m, const char *host, int host_len, const char *path, int path_len,
        int match(struct urlmatch *m, urlmatch_pattern_t *urlmatch_pattern, const char *host, int host_len, const char *path, int path_len, int match_host_pos, int match_path_pos, void *context),
        void *context)
{
    urlmatch_state_t *urlmatch_state = &m->root_state;
    urlmatch_pattern_t *urlmatch_pattern;
    int i;
    for (i = host_len-1; i >= 0; i--){
        unsigned char next_state_pos = m->X[(unsigned char)host[i]]; if (urlmatch_state->next2 == NULL) return NULL;
        urlmatch_state = urlmatch_state->next2[next_state_pos];
        if (urlmatch_state == NULL) return NULL;
        for(urlmatch_pattern = urlmatch_state->urlmatch_pattern; urlmatch_pattern; urlmatch_pattern = urlmatch_pattern->next) {
            if (match == NULL) return urlmatch_pattern;
            if (match(m, urlmatch_pattern, host, host_len, path, path_len, i, -1, context) > 0) return urlmatch_pattern;
        }
    }
    for (i = 0; i < path_len; i++){
        unsigned char next_state_pos = m->X[(unsigned char)path[i]]; if (urlmatch_state->next2 == NULL) return NULL;
        urlmatch_state = urlmatch_state->next2[next_state_pos];
        if (urlmatch_state == NULL) return NULL;
        for(urlmatch_pattern = urlmatch_state->urlmatch_pattern; urlmatch_pattern; urlmatch_pattern = urlmatch_pattern->next) {
            if (match == NULL) return urlmatch_pattern;
            if (match(m, urlmatch_pattern, host, host_len, path, path_len, 0, i, context) > 0) return urlmatch_pattern;
        }
    }
    return NULL;
}

#ifdef WIN32
static inline void* memmem(const void* haystack, size_t haystackLen, const void* needle, size_t needleLen)
{
	if (needleLen == 0 || haystack == needle) return (void*)haystack;
	if (haystack == NULL || needle == NULL) return NULL;

	const unsigned char* haystackStart = (const unsigned char*)haystack;
	const unsigned char* needleStart = (const unsigned char*)needle;
	const unsigned char needleEndChr = *(needleStart + needleLen - 1);

	++haystackLen;
	for (; --haystackLen >= needleLen; ++haystackStart) {
		size_t x = needleLen;
		const unsigned char* n = needleStart;
		const unsigned char* h = haystackStart;

		if (*haystackStart != *needleStart || *(haystackStart + needleLen - 1) != needleEndChr)
			continue;

		while (--x > 0) {
			if (*h++ != *n++) {
				break;
			}
		}
		if (x == 0) return (void*)haystackStart;
	}
	return NULL;
}
#endif
static inline int urlmatch_add_url_extra(struct urlmatch *m, const char *host, int host_len, const char *path, int path_len, void *userdata, int update)
{
    int i;
    char a;

    for (i = 0; i < host_len; i++) { a = host[i]; if (!memmem(m->char_list, m->char_list_len, &a, 1)) { URLMATCH_ERR("host[%.*s] contain special char 0x%02x [%c]\n", host_len, host, (uint8_t)a, a); return -1; } }
    for (i = 0; i < path_len; i++) { a = path[i]; if (!memmem(m->char_list, m->char_list_len, &a, 1)) { URLMATCH_ERR("path[%.*s] contain special char 0x%02x [%c] [host %.*s]\n", path_len, path, (uint8_t)a, a, host_len, host); return -1; } }
    if (update) {
        urlmatch_pattern_t *t = urlmatch_find(m, host, host_len, path, path_len, NULL, NULL);
        if (t) {
            if (t->userdata) { if (m->urlmatch_userfree) m->urlmatch_userfree(t->userdata); else free(t->userdata); }
            t->userdata = userdata;
            return 0;
        }
    }
    urlmatch_pattern_t *urlmatch_pattern = calloc(1, sizeof(urlmatch_pattern_t)); if (urlmatch_pattern == NULL) { URLMATCH_ERR("fail to calloc\n"); return -1; }
    m->pattern_mem += sizeof(urlmatch_pattern_t);
    m->pattern_count++;
    urlmatch_pattern->userdata = userdata;

    urlmatch_state_t *urlmatch_state = &m->root_state;

    for (i = host_len - 1; i >= 0; i--) {
        unsigned char next_state_pos = m->X[(unsigned char)host[i]];
        if (urlmatch_state->next2 == NULL) { urlmatch_state->next2 = calloc(m->char_list_len, sizeof(void *)); if (urlmatch_state->next2 == NULL) return -1;
            m->stat_array_mem += m->char_list_len * sizeof(void *);
            m->stat_array_count++;
        }
        if (urlmatch_state->next2[next_state_pos] == NULL) {
            urlmatch_state->next2[next_state_pos] = calloc(1, sizeof(urlmatch_state_t)); if (urlmatch_state->next2[next_state_pos] == NULL) { URLMATCH_ERR("fail to calloc[%m]\n"); return -1; }
            m->state_mem += sizeof(urlmatch_state_t);
            m->state_count++;
            list_add_tail(&urlmatch_state->next2[next_state_pos]->node, &m->state_list);
        }
        urlmatch_state = urlmatch_state->next2[next_state_pos];
    }

    for (i = 0; i < path_len; i++) {
        unsigned char next_state_pos = m->X[(unsigned char)path[i]];
        if (urlmatch_state->next2 == NULL) { urlmatch_state->next2 = calloc(m->char_list_len, sizeof(void *)); if (urlmatch_state->next2 == NULL) return -1;
            m->stat_array_mem += m->char_list_len * sizeof(void *);
            m->stat_array_count++;
        }
        if (urlmatch_state->next2[next_state_pos] == NULL) {
            urlmatch_state->next2[next_state_pos] = calloc(1, sizeof(urlmatch_state_t)); if (urlmatch_state->next2[next_state_pos] == NULL) { URLMATCH_ERR("fail to calloc[%m]\n"); return -1; }
            m->state_mem += sizeof(urlmatch_state_t);
            m->state_count++;
            list_add_tail(&urlmatch_state->next2[next_state_pos]->node, &m->state_list);
        }
        urlmatch_state = urlmatch_state->next2[next_state_pos];
    }
    urlmatch_pattern->next = urlmatch_state->urlmatch_pattern;
    urlmatch_state->urlmatch_pattern = urlmatch_pattern;
    m->item_count++;
    return 0;
}
static inline int urlmatch_add_url(struct urlmatch *m, const char *url, void *userdata)
{
    if (url == NULL) return -1;
    int url_len = strlen(url);
    const char *host = url;
    const char *path = memchr(url, '/', url_len); if (path == NULL) path = url + url_len;
    int host_len = path - host;
    int path_len = url_len - host_len;

    return urlmatch_add_url_extra(m, host, host_len, path, path_len, userdata, 1);
}

static inline struct urlmatch *urlmatch_new(URLMATCH_USERFREE urlmatch_userfree, void *char_list, int char_list_len)
{
    unsigned i;
    unsigned n = 0;
    struct urlmatch *m = calloc(1, sizeof(struct urlmatch)); if (m == NULL) { URLMATCH_ERR("fail to calloc[%m]\n"); return NULL; }
    m->char_list = malloc(char_list_len);
    m->char_list_len = char_list_len;
    memcpy(m->char_list, char_list, char_list_len);
    for (i = 0; i < char_list_len; i++) {
        m->X[m->char_list[i]] = n;
        n++;
    }
    m->urlmatch_userfree = urlmatch_userfree;
    INIT_LIST_HEAD(&m->state_list);
    return m;
}

static inline void urlmatch_free(struct urlmatch *m)
{
    if (m == NULL) return;

    urlmatch_state_t *state, *n;
    list_for_each_entry_safe(state, n, &m->state_list, node) {
        list_del(&state->node);

        urlmatch_pattern_t *urlmatch_pattern = state->urlmatch_pattern;
        while (urlmatch_pattern) {
            urlmatch_pattern_t *urlmatch_pattern_next = urlmatch_pattern->next;
            if (urlmatch_pattern->userdata) {
                if (m->urlmatch_userfree) m->urlmatch_userfree(urlmatch_pattern->userdata); else free(urlmatch_pattern->userdata);
            }
            free(urlmatch_pattern);
            urlmatch_pattern = urlmatch_pattern_next;
        }
        if (state->next2) free(state->next2);
        free(state);
    }
    free(m);
}

static inline void urlmatch_stat(struct urlmatch *m)
{
    printf("item_count %u\n", m->item_count);
    printf("pattern     size %3u count %-10u mem %5"PRIu64"m %"PRIu64"\n", (int)sizeof(urlmatch_pattern_t)       , m->pattern_count   , m->pattern_mem   /1000000, m->pattern_mem   );
    printf("state       size %3u count %-10u mem %5"PRIu64"m %"PRIu64"\n", (int)sizeof(urlmatch_state_t)         , m->state_count     , m->state_mem     /1000000, m->state_mem     );
    printf("state_array size %3u count %-10"PRIu64" mem %5"PRIu64"m %"PRIu64"\n", m->char_list_len * (int)sizeof(void *), m->stat_array_count, m->stat_array_mem/1000000, m->stat_array_mem);
}

#endif
